package com.chb.link;

/**
 * 约瑟夫环问题
 * <p>
 * 单向循环
 */
public class JosephusRing {
    public static void main(String[] args) {
        JosephusRingList jrList = new JosephusRingList();
        jrList.addNodes(5);
        jrList.showLink();

        // 出圈
        jrList.outOfRing(1, 2);

    }
}

class JosephusRingList {
    SingleListNode head = null;

    /**
     * 构建约瑟夫环
     *
     * @param nums
     */
    public void addNodes(int nums) {
        SingleListNode tmp = null;  // 指向新加入的节点
        for (int i = 1; i <= nums; i++) {
            SingleListNode curNode = new SingleListNode(i); // 待加入的节点
            if (i == 1) { // 加入第一个节点
                head = curNode;
            } else {
                tmp.next = curNode;
            }
            curNode.next = head; // 形成环状
            tmp = curNode;
        }
    }

    /**
     * 打印链表
     */
    public void showLink() {
        SingleListNode tmp = head;
        System.out.print(head.val);
        while (tmp.next != head) {
            System.out.print("->" + tmp.next.val);
            tmp = tmp.next;
        }
        System.out.println();
    }

    /**
     * 出圈
     *
     * @param startNo  开始的位置
     * @param countNum 计算，说多少下，出圈
     */
    public void outOfRing(int startNo, int countNum) {
        System.out.println("out of ring");
        SingleListNode helperNode = head;
        // helperNode指向最后一个节点
        while (helperNode.next != head) {
            helperNode = helperNode.next;

        }

        // 移动到startNo的位置
        for (int i = 1; i < startNo; i++) {
            helperNode = helperNode.next;
            head = head.next;
        }

        int count = 1;
        while (helperNode != head) { // 退出循环： 只有一个节点
            // System.out.println(count + "," + countNum + "," + head.val + "," + helperNode.val);
            if (count == countNum) { //出圈
                System.out.println("Node " + head.val + " out");
                head = head.next;
                helperNode.next = head;
                count = 1; // 重新计数
            }
            head = head.next;
            helperNode = helperNode.next;
            count++;
        }
        System.out.println("Node " + helperNode.val + " out");


    }

}
